{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Beauty of an Array After Applying Operation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBeauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组的最大美丽值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 和一个 <strong>非负</strong> 整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>在一步操作中，你可以执行下述指令：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在范围&nbsp;<code>[0, nums.length - 1]</code> 中选择一个 <strong>此前没有选过</strong> 的下标 <code>i</code> 。</li>\n",
    "\t<li>将 <code>nums[i]</code> 替换为范围 <code>[nums[i] - k, nums[i] + k]</code> 内的任一整数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>数组的 <strong>美丽值</strong> 定义为数组中由相等元素组成的最长子序列的长度。</p>\n",
    "\n",
    "<p>对数组 <code>nums</code> 执行上述操作任意次后，返回数组可能取得的 <strong>最大</strong> 美丽值。</p>\n",
    "\n",
    "<p><strong>注意：</strong>你 <strong>只</strong> 能对每个下标执行 <strong>一次</strong> 此操作。</p>\n",
    "\n",
    "<p>数组的 <strong>子序列</strong> 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,6,1,2], k = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>在这个示例中，我们执行下述操作：\n",
    "- 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。\n",
    "- 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。\n",
    "执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。\n",
    "可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1,1,1], k = 10\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>在这个示例中，我们无需执行任何操作。\n",
    "数组 nums 的美丽值是 4（整个数组）。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i], k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-beauty-of-an-array-after-applying-operation](https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-beauty-of-an-array-after-applying-operation](https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,6,1,2]\\n2', '[1,1,1,1]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        m = 0\n",
    "        for i in range(len(nums)):\n",
    "            a = bisect.bisect(nums,nums[i]+2*k)\n",
    "            if a-i>m:\n",
    "                m = a-i\n",
    "        return m\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, a: List[int], k: int) -> int:\n",
    "        l=min(a)-k\n",
    "        r=max(a)+k\n",
    "        ans=0\n",
    "        from sortedcontainers import SortedList\n",
    "        s=SortedList(a)\n",
    "        for i in range(l,r+1):\n",
    "            k1=s.bisect_left(i-k)\n",
    "            k2=s.bisect_right(i+k)\n",
    "            ans=max(ans,k2-k1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        M = 100010\n",
    "        cnt = [0] * M\n",
    "        for v in nums:\n",
    "            cnt[max(v - k, 0)] += 1\n",
    "            cnt[min(v + k + 1, M - 1)] -= 1\n",
    "        ans = cur = 0\n",
    "        for v in cnt:\n",
    "            cur += v\n",
    "            ans = max(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        k=k*2\n",
    "        b=big =1\n",
    "        i=j=0\n",
    "        for i,v in enumerate(nums):\n",
    "            t=v+k \n",
    "            while j<n and nums[j]<=t:\n",
    "                j+=1\n",
    "            if (t:=j-i)>b:\n",
    "                b=t\n",
    "            if j==n:return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left = 0\n",
    "        for n in nums:\n",
    "            if n - nums[left] > 2 * k:\n",
    "                left += 1\n",
    "        return len(nums) - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        a = [0] * (100002)\n",
    "        for x in nums:\n",
    "            a[max(x - k, 0)] += 1\n",
    "            a[min(x + k + 1, 100001)] -= 1\n",
    "        for i in range(1, len(a)):\n",
    "            a[i] += a[i-1]\n",
    "        return max(a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "\n",
    "        n = len(nums)\n",
    "        left, ans = 0, 0\n",
    "\n",
    "        for right in range(n):\n",
    "            while nums[right] - nums[left] > 2 * k:\n",
    "                left += 1\n",
    "            ans = max(ans, right - left + 1)\n",
    "                \n",
    "\n",
    "        ans = max(ans, right - left + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans, deq = 0, deque()\n",
    "        for num in nums:\n",
    "            deq.append(num)\n",
    "            while deq[0] +k < deq[-1] -k: deq.popleft()\n",
    "            ans = max(ans, len(deq))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        # 差分数组 i到j的所有数值加1，等价于d[i]+=1,d[j+1]-=1\n",
    "        # 初始全部为0，最后求前缀和，然后算最大值\n",
    "        min_n = min(nums) - k\n",
    "        max_n = max(nums) + k\n",
    "        d = [0 for _ in range(min_n, max_n + 2)]\n",
    "        for l in range(len(nums)):\n",
    "            i = nums[l] - k\n",
    "            j = nums[l] + k\n",
    "            d[i - min_n] += 1\n",
    "            # print(j, min_n, d)\n",
    "            d[j - min_n + 1] -= 1\n",
    "        res = 0\n",
    "        tmp = 0\n",
    "        for i in range(len(d)):\n",
    "            tmp += d[i]\n",
    "            res = max(res, tmp)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        s=[0 for _ in range(max(nums)+2*k+1)]\n",
    "        for n in nums:\n",
    "            s[n]+=1\n",
    "            if n+2*k+1<len(s): s[n+2*k+1]-=1\n",
    "\n",
    "        res,count=1,0\n",
    "        for c in s:\n",
    "            count+=c\n",
    "            res=max(res,count)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # d = np.zeros((300001, ), dtype=int)\n",
    "        d = [0] * 300002\n",
    "        lb = 10000000\n",
    "        ub = -10000000\n",
    "        for x in nums:\n",
    "            d[x - k + 100000] += 1\n",
    "            d[x + k + 100001] -= 1\n",
    "            lb = min(lb, x)\n",
    "            ub = max(ub, x)\n",
    "        acc = 0\n",
    "        ans = 0\n",
    "        for i in range(lb - k, ub + k + 2):\n",
    "            acc += d[i + 100000]\n",
    "            ans = max(ans, acc)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        maxn=max(nums)\n",
    "        ng=maxn+k+k+2\n",
    "        g=[0]*ng\n",
    "        for a in nums:\n",
    "            g[a]+=1\n",
    "            g[a+k+k+1]-=1\n",
    "        res=rt=0\n",
    "        for a in g:\n",
    "            rt+=a\n",
    "            res=max(res,rt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        l=0\n",
    "        r=0\n",
    "        nums.sort()\n",
    "        q=[0]\n",
    "        for x in nums:\n",
    "            q.append(q[-1]+x)\n",
    "        n=len(nums)\n",
    "        s=0\n",
    "        ans=0\n",
    "        print(q)\n",
    "        while r<n:\n",
    "          while nums[r]-nums[l]>2*k:\n",
    "              l+=1\n",
    "          ans=max(ans,r-l+1)    \n",
    "          r+=1\n",
    "        return ans  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        low = [x - k for x in nums]\n",
    "        high = [x + k for x in nums]\n",
    "        n = len(nums)\n",
    "        # i = 0\n",
    "        pre, ans = high[0] - 1  , 0\n",
    "        for i in range(n):\n",
    "            if high[i] > pre:\n",
    "                ans = max(ans, bisect_right(low, high[i]) - i)\n",
    "                # ans = max(ans, bisect_left(low[i:], high[i]))\n",
    "            else:\n",
    "                continue\n",
    "            pre = high[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        res = [0] * (2 * 10 ** 5 + 10) \n",
    "        n = len(nums) \n",
    "        ans = 0 \n",
    "        m = max(nums)\n",
    "        for i, x in enumerate(nums) : \n",
    "            t = max(0, x - k) \n",
    "            res[t] += 1 \n",
    "            res[x + k + 1] -= 1 \n",
    "        for i in range(1, m + k + 2) : \n",
    "            res[i] += res[i - 1] \n",
    "            ans = max(ans, res[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return Counter(nums).most_common(1)[0][1]\n",
    "        k *= 2\n",
    "        nums.sort()\n",
    "        m, t = 1, nums.pop() - k\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] >= t:\n",
    "                continue\n",
    "            m = max(m, len(nums) - i)\n",
    "            t = nums.pop() - k\n",
    "        return max(m, len(nums) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:\n",
    "            return Counter(nums).most_common(1)[0][1]\n",
    "        k *= 2\n",
    "        nums.sort()\n",
    "        m, t = 1, nums.pop() - k\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if nums[i] >= t:\n",
    "                continue\n",
    "            m = max(m, len(nums) - i)\n",
    "            t = nums.pop() - k\n",
    "        return max(m, len(nums) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        start, end = [], []\n",
    "        for num in nums:\n",
    "            start.append(num - k)\n",
    "            end.append(num + k)\n",
    "        start.sort()\n",
    "        end.sort()\n",
    "        l = r = 0\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        while l < len(nums):\n",
    "            if start[l] <= end[r]:\n",
    "                cnt += 1\n",
    "                ans = max(ans, cnt)\n",
    "                l += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "                r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "            nums.sort()\n",
    "            t = [0] * (nums[-1] + k + 5)\n",
    "            for i in nums:\n",
    "                \n",
    "                t[max(0,i-k)] += 1\n",
    "                t[i+k+1] -= 1\n",
    "            for i in range(1,len(t)):\n",
    "                t[i] += t[i-1]\n",
    "            j = 0\n",
    "            for i in range(len(t)):\n",
    "                if t[j] < t[i]:\n",
    "                    j = i\n",
    "            \n",
    "            return t[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        diff = [0]*200010\n",
    "        # base = [0]*200010\n",
    "        count = [0]*200010\n",
    "        for num in nums:\n",
    "            start = num -k\n",
    "            end = num + k\n",
    "            if start >= 0:\n",
    "                diff[start] += 1\n",
    "            \n",
    "            if end <= 100000:\n",
    "                diff[end+1] -= 1\n",
    "                \n",
    "        val = 0\n",
    "        for i,y in enumerate(diff):\n",
    "            val += y\n",
    "            count[i] = val\n",
    "        \n",
    "        max_index = count.index(max(count))\n",
    "        \n",
    "        re = 0\n",
    "        for num in nums:\n",
    "            if max_index >= num-k and max_index<= num+k:\n",
    "                re += 1\n",
    "                \n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "\n",
    "        left_bound_list = []\n",
    "        right_bound_list = []\n",
    "\n",
    "        for idx in range(n):\n",
    "            left_bound_list.append(nums[idx] - k)\n",
    "            right_bound_list.append(nums[idx] + k)\n",
    "        \n",
    "        pl, pr = 0, 0\n",
    "\n",
    "        res = -float('inf')\n",
    "        while pl < n:\n",
    "\n",
    "            if left_bound_list[pl] <= right_bound_list[pr]:\n",
    "                pl += 1\n",
    "                res = max(res, pl - pr)\n",
    "            else:\n",
    "                pr += 1\n",
    "                res = max(res, pl - pr)\n",
    "        \n",
    "        res = max(res, pl - pr)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums, k: int):\n",
    "        ###方法3 差分数组\n",
    "        n = len(nums)\n",
    "        max_value = max(nums) + k\n",
    "        diff = [0] * (max_value+1)\n",
    "        for i, x in enumerate(nums):\n",
    "            left = x - k if (x-k) >= 0 else 0\n",
    "            diff[left] += 1\n",
    "            right = x + k + 1 if (x+k+1) <= max_value else max_value\n",
    "            diff[right] -= 1\n",
    "        print(diff)\n",
    "        res = diff[0]\n",
    "        for i in range(1, len(diff)):\n",
    "            diff[i] += diff[i-1]\n",
    "            res = max(res, diff[i])\n",
    "        return res\n",
    "\n",
    "        ###方法2，先排序，再找相差不超过2k的序列长度\n",
    "        # nums.sort()\n",
    "        # n = len(nums)\n",
    "        # fast, slow = 0, 0\n",
    "        # max_len = 0\n",
    "        # while fast < n:\n",
    "        #     if nums[fast] - nums[slow] <= 2*k:\n",
    "        #         length = fast - slow + 1\n",
    "        #         fast += 1\n",
    "        #         if length > max_len:\n",
    "        #             max_len = length\n",
    "        #     else:\n",
    "        #         slow += 1\n",
    "        # return max_len\n",
    "\n",
    "\n",
    "        ###方法1，用数组记录，超时\n",
    "        # n = len(nums)\n",
    "        # min_value = min(nums) - k\n",
    "        # max_value = max(nums) + k\n",
    "        # m = max_value - min_value + 1\n",
    "        # array = [[0] * m for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     min_index = nums[i] - k - min_value\n",
    "        #     max_index = nums[i] + k - min_value\n",
    "        #     len_arr = max_index - min_index + 1\n",
    "        #     array[i][min_index : max_index+1] = [1] * len_arr\n",
    "        # res = max(list(map(sum, zip(*array))))\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        previous_end = [nums[0] + k]\n",
    "        previous_number = [1]\n",
    "        for i in range(1, len(nums)):\n",
    "            c_number = 1\n",
    "            begin = nums[i] - k\n",
    "            end = nums[i] + k\n",
    "            previous_number.append(len(previous_end) - self.find_element(previous_end, begin) + 1)\n",
    "            \n",
    "            previous_end.append(end)\n",
    "        return max(previous_number)\n",
    "            \n",
    "    def find_element(self, nums, target):\n",
    "        length = len(nums)\n",
    "        if target > nums[-1]:\n",
    "            return length\n",
    "        elif target <= nums[0]:\n",
    "            return 0\n",
    "        begin = 0\n",
    "        end = length - 1\n",
    "        while end > begin + 1:\n",
    "            mid = (begin + end) // 2\n",
    "            if nums[mid] >= target:\n",
    "                end = mid\n",
    "            else:\n",
    "                begin = mid\n",
    "        return end\n",
    "                \n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        cnt = {}\n",
    "        for r in range(n):\n",
    "            while nums[r] - nums[l] > 2 * k:\n",
    "                l += 1\n",
    "            cnt[l] = r - l + 1\n",
    "        return max(cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if len(set(nums)) == 1:return n\n",
    "        dic = [0] * (max(nums) + 2)\n",
    "        for i in range(n):\n",
    "            i = nums[i]\n",
    "            dic[max(0, i-k)] += 1  \n",
    "            dic[min(i+k+1, len(dic) - 1)] -= 1  \n",
    "        for i in range(1, len(dic)):\n",
    "            dic[i] += dic[i-1]  \n",
    "        return max(dic)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        ctr = Counter(nums)\n",
    "        \n",
    "        res = 0\n",
    "        tmp = sum(ctr[i] for i in range(min(ctr), min(ctr) + k))\n",
    "        for i in range(min(ctr), max(ctr) + 1):\n",
    "            tmp += ctr[i + k] - ctr[i - k - 1]\n",
    "            res = max(res, tmp)\n",
    "            \n",
    "            # print(i, tmp, res)\n",
    "    \n",
    "        return res\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter(nums)\n",
    "        sort = sorted(c)\n",
    "        # 滑动窗口\n",
    "        right = 0\n",
    "        n = len(sort)\n",
    "        ans = sum_ = 0\n",
    "        k <<= 1\n",
    "        for x in sort:\n",
    "            while right < n and x + k >= sort[right]:\n",
    "                sum_ += c[sort[right]]\n",
    "                right += 1\n",
    "            if sum_ > ans:\n",
    "                ans = sum_\n",
    "            if right == n:\n",
    "                break\n",
    "            sum_ -= c[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        c = Counter(nums)\n",
    "        sort = sorted(c)\n",
    "        # 滑动窗口\n",
    "        right = 0\n",
    "        n = len(sort)\n",
    "        ans = sum_ = 0\n",
    "        k <<= 1\n",
    "        for x in sort:\n",
    "            while right < n and x + k >= sort[right]:\n",
    "                sum_ += c[sort[right]]\n",
    "                right += 1\n",
    "            if sum_ > ans:\n",
    "                ans = sum_\n",
    "            if right == n:\n",
    "                break\n",
    "            sum_ -= c[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        num_dict = dict()\n",
    "        for num in nums:\n",
    "            if num not in num_dict:\n",
    "                num_dict[num] = 0\n",
    "            num_dict[num] += 1\n",
    "        \n",
    "        max_num = 0\n",
    "        min_num = min(num_dict.keys())\n",
    "        max_num = max(num_dict.keys())\n",
    "        \n",
    "        num_list = [0 for i in range(min_num, max_num+1)]\n",
    "\n",
    "        for i in range(len(num_list)):\n",
    "            num = min_num + i\n",
    "            if i == 0 or i == len(num_list) - 1:\n",
    "                total_sum = 0\n",
    "                for new_num in range(num-k, num+k+1):\n",
    "                    try:\n",
    "                        total_sum += num_dict[new_num]\n",
    "                    except:\n",
    "                        pass\n",
    "                num_list[i] = total_sum\n",
    "            else:\n",
    "                num_list[i] = num_list[i-1]\n",
    "                try:\n",
    "                    num_list[i] -= num_dict[num-k-1]\n",
    "                except:\n",
    "                    pass\n",
    "                \n",
    "                try:\n",
    "                    num_list[i] += num_dict[num+k]\n",
    "                except:\n",
    "                    pass\n",
    "        return max(num_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ma = max(nums)\n",
    "        arr = [0] * (2 * k + ma + 10)\n",
    "        m = int(1e5)\n",
    "        for i in nums:\n",
    "            arr[i - k + k] += 1\n",
    "            arr[i + k + k + 1] -= 1\n",
    "        res = 0\n",
    "        for i in range(1,len(arr)):\n",
    "            arr[i] += arr[i - 1]\n",
    "            res = max(res,arr[i])\n",
    "        return res    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        # ans = 0\n",
    "        # l = min(nums) - k\n",
    "        # h = max(nums) + k\n",
    "        # for x in range(l, h + 1):\n",
    "        #     cnt = sum([1 if (num - k <= x and num + k >= x) else 0 for num in nums ])\n",
    "        #     ans = max(ans, cnt)\n",
    "        # return ans\n",
    "        l = min(nums) - k\n",
    "        h = max(nums) + k\n",
    "        m = h - l + 3\n",
    "        diff = [0] * m\n",
    "        for num in nums:\n",
    "            low, high = num - k, num + k\n",
    "            diff[low - l + 1] += 1\n",
    "            diff[high - l + 2] -= 1\n",
    "        for i in range(1, len(diff)):\n",
    "            diff[i] += diff[i - 1]\n",
    "        return max(diff)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        d = [0] * 400010\n",
    "        t = 200000\n",
    "        r = -1\n",
    "        l = inf\n",
    "        for x in nums:\n",
    "            d[x - k + t] += 1\n",
    "            d[x + k + t + 1] -= 1\n",
    "            l = min(l, x - k + t)\n",
    "            r = max(r, x + k + t + 1)\n",
    "        res = -1\n",
    "        mx = -1\n",
    "        for i in range(l, r + 1):\n",
    "            d[i] += d[i - 1]\n",
    "            if d[i] > mx:\n",
    "                mx = d[i]\n",
    "                res = i\n",
    "        \n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        # 用排序后的数组和累积和数组\n",
    "        sortedNums = sorted([(num, i) for i, num in enumerate(nums)])\n",
    "        prefixSum = [0]\n",
    "        for num, _ in sortedNums:\n",
    "            prefixSum.append(prefixSum[-1] + 1)\n",
    "\n",
    "        # 查找每个nums[i] 到 nums[i] + 2k范围的数有多少个\n",
    "        maximumBeauty = 0\n",
    "        for num, i in sortedNums:\n",
    "            left = bisect.bisect_left(sortedNums, (num,i))  \n",
    "            right = bisect.bisect_right(sortedNums, (num+2*k, len(nums)))\n",
    "            maximumBeauty = max(maximumBeauty, prefixSum[right] - prefixSum[left])\n",
    "\n",
    "        return maximumBeauty\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "from queue import PriorityQueue as PQ\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = []\n",
    "        for num in nums:\n",
    "            cnt.append((num-k,num+k))\n",
    "        cnt.sort()\n",
    "        h = PQ()\n",
    "        h.put(cnt[0][1])\n",
    "        k = 1\n",
    "        ans = 1\n",
    "        for i in range(1,n):\n",
    "            h.put(cnt[i][1])\n",
    "            k += 1\n",
    "            a = h.get()\n",
    "            while cnt[i][0] > a:\n",
    "                a = h.get()\n",
    "                k -= 1\n",
    "            h.put(a)\n",
    "            ans = max(ans,k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        dq = deque()\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            dq.append((x-k, x+k))\n",
    "            while dq and dq[0][1] < dq[-1][0]:\n",
    "                dq.popleft()\n",
    "            ans = max(ans, len(dq))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        d = defaultdict()\n",
    "        for i, x in enumerate(nums):\n",
    "            if not d.get(x): d[x] = 1\n",
    "            else: d[x] += 1\n",
    "        ans = 0\n",
    "        cnt = [0] * (max(nums) + k + 1)\n",
    "        for i in range(max(nums) + k):\n",
    "            if d.get(i) is not None: cnt[i+1] = d.get(i)\n",
    "            cnt[i+1] += cnt[i]\n",
    "            ans = max(ans, cnt[i+1] - cnt[max(0, i - 2 * k)])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ret = 1\n",
    "        arr = [[n-k, n+k] for n in nums]\n",
    "        l = 0\n",
    "        for r in range(1, len(nums)):\n",
    "            while l < r and arr[l][1] < arr[r][0]:\n",
    "                l += 1\n",
    "            ret = max(ret, r-l+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        points = []\n",
    "        for num in nums:\n",
    "            points.append([num-k, num+k])\n",
    "        points.sort()\n",
    "        res = 1\n",
    "        left = 0\n",
    "        for i in range(1, len(points)):\n",
    "            while points[i][0] > points[left][1]:\n",
    "                left += 1\n",
    "            res = max(res, i-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        num_count_list = sorted(collections.Counter(nums).items(), key = lambda x:x[0])\n",
    "        cur = ret = 0\n",
    "        i = 0\n",
    "        for num, count in num_count_list:\n",
    "            while num_count_list[i][0] + 2 * k < num:\n",
    "                cur -= num_count_list[i][1]\n",
    "                i += 1\n",
    "            cur += count\n",
    "            if cur > ret:\n",
    "                ret = cur\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        cnt = {}\n",
    "        for num in nums:\n",
    "            cnt[num] = cnt.get(num, 0) + 1\n",
    "\n",
    "        cntList = [(n, c) for n, c in cnt.items()]\n",
    "        cntList.sort()\n",
    "        res = 0\n",
    "        rangeSum = 0\n",
    "        l = 0\n",
    "        r = 0\n",
    "        print(cntList)\n",
    "        while r < len(nums):\n",
    "            while r < len(cntList) and cntList[r][0] - cntList[l][0] <= k * 2:\n",
    "                rangeSum += cntList[r][1]\n",
    "                r += 1\n",
    "            res = max(res, rangeSum)\n",
    "            if r >= len(cntList):\n",
    "                break\n",
    "            while l < len(cntList) and cntList[r][0] - cntList[l][0] > k * 2:\n",
    "                rangeSum -= cntList[l][1]\n",
    "                l += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        arr=[]\n",
    "        for i in range(n):\n",
    "            arr.append([nums[i]-k,nums[i]+k])\n",
    "        arr.sort(key=lambda x:x[0])\n",
    "        a,b=0,0\n",
    "        ans=0\n",
    "        if arr[-1][0]<=arr[0][1]:\n",
    "            return n\n",
    "        while b<n:\n",
    "            if arr[b][0]<=arr[a][1]:\n",
    "                b+=1\n",
    "            else:\n",
    "                a+=1\n",
    "            ans=max(ans,b-a)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        zones = []\n",
    "        \n",
    "        for num in nums:\n",
    "            zones.append([num-k,num+k])\n",
    "        \n",
    "        zones.sort(key = lambda x: x[0])\n",
    "        stack = deque()\n",
    "        res = 0\n",
    "        for zone in zones:\n",
    "            while stack and stack[0]<zone[0]:\n",
    "                stack.popleft()\n",
    "            stack.append(zone[1])\n",
    "            res = max(res,len(stack))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        sps = []\n",
    "        for i in range(len(nums)):\n",
    "            sps.append((nums[i]-k, nums[i]+k))\n",
    "        sps.sort()\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        for i in range(len(sps)):\n",
    "            while q and sps[q[0]][1] < sps[i][0]:\n",
    "                q.popleft()\n",
    "            q.append(i)\n",
    "            ans = max(ans, len(q))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ra = [(n - k, n + k) for n in nums]\n",
    "        \n",
    "        print(ra)\n",
    "        ans = 1\n",
    "        tmp = 1\n",
    "        s = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if ra[i][0] <= ra[s][1]:\n",
    "                tmp += 1\n",
    "                ans = max(ans, tmp)\n",
    "            else:\n",
    "                while ra[i][0] > ra[s][1]:\n",
    "                    s += 1\n",
    "                    tmp -= 1\n",
    "                tmp += 1\n",
    "        \n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        cct=-1\n",
    "        c=Counter(nums)\n",
    "        l=len(nums)\n",
    "        s1=sorted(list(set(nums))) #sortednum\n",
    "        s2=[0]\n",
    "        for i in reversed(s1):\n",
    "            s2.append(s2[-1]+c[i])\n",
    "        s2=s2[::-1]\n",
    "        s1.append(4*10**5)\n",
    "        for i in range(len(s1)-1):\n",
    "            rightspot=bisect.bisect(s1,s1[i]+2*k)\n",
    "            cct=max(cct,s2[i]-s2[rightspot])\n",
    "        return cct\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        b = set(nums)\n",
    "        if len(b) ==  1:\n",
    "            return len(nums)\n",
    "        ma = max(nums)    \n",
    "        arr = [0] * (2 * k + ma + 2)\n",
    "        for i in nums:\n",
    "            arr[i] += 1\n",
    "            arr[i + 2 * k + 1] -= 1 \n",
    "        for i in range(1,len(arr)):\n",
    "            arr[i] += arr[i - 1] \n",
    "        ma = max(arr)\n",
    "        return ma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        arr = []\n",
    "        minx, maxx = float('inf'), float('-inf')\n",
    "        for x in nums:\n",
    "            arr.append([x-k, x+k])\n",
    "            minx = min(minx, x-k)\n",
    "            maxx = max(maxx, x+k)\n",
    "        c = -minx \n",
    "        d = [0] * (maxx + c + 2)\n",
    "        for [x, y] in arr:\n",
    "            d[x+c] += 1\n",
    "            d[y+c+1] -= 1\n",
    "        f = 0\n",
    "        ans = 0 \n",
    "        for i in range(maxx + c+1):\n",
    "            f += d[i]\n",
    "            ans = max(ans, f)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        mn, mx = min(cnt), max(cnt)\n",
    "        res = [0] * (mx - mn + 2 * k + 2)\n",
    "        st = mn - k\n",
    "        for x in cnt:\n",
    "            res[x - k - st] += cnt[x]\n",
    "            res[x + k - st + 1] -= cnt[x]\n",
    "            \n",
    "        ans = res[0]\n",
    "        for i in range(1, len(res)):\n",
    "            res[i] += res[i - 1]\n",
    "            ans = max(ans, res[i])\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        v = sorted(cnt.items(), key=lambda x: x[0])\n",
    "        keys = [a for a, b in v]\n",
    "        vals = [b for a, b in v]\n",
    "        for i in range(1, len(vals)):\n",
    "            vals[i] += vals[i-1]\n",
    "\n",
    "        res = 0\n",
    "        for i, v in enumerate(keys):\n",
    "            l, r = bisect.bisect_left(keys, v), bisect.bisect_right(keys, v + k + k)\n",
    "            if l == 0:\n",
    "                res = max(res, vals[r - 1])\n",
    "            else:\n",
    "                res = max(res, vals[r - 1] - vals[l-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        counter = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            counter[max(1, num - k)] += 1\n",
    "            counter[num + k + 1] -= 1\n",
    "        counter = sorted(counter.items())\n",
    "        \n",
    "        curr = 0\n",
    "        ans = 0\n",
    "        # print(counter)\n",
    "        for idx, plus in counter:\n",
    "            # print(idx, plus)\n",
    "            curr += plus\n",
    "            ans = max(ans, curr)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # mapp = {}\n",
    "        # max_num = -9999\n",
    "        # for i in range(n):\n",
    "        #     for j in range(nums[i]-k,nums[i]+k+1):\n",
    "        #         if j not in mapp:\n",
    "        #             mapp[j]=1\n",
    "        #         else:\n",
    "        #             mapp[j]+=1\n",
    "        #         max_num = max(mapp[j],max_num)\n",
    "\n",
    "        # return max_num\n",
    "        n = len(nums)\n",
    "        nums = sorted(nums)\n",
    "        # 有多少个集合相交\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        for j, x in enumerate(nums):\n",
    "            while x - nums[i] > k * 2:\n",
    "                i += 1\n",
    "            ans = max(ans, j - i + 1)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        # 数飞机\n",
    "        arr = []\n",
    "        for i in nums:\n",
    "            # 上升是-1，下降是1\n",
    "            arr.append((i-k,-1))\n",
    "            arr.append((i+k,1))\n",
    "        arr.sort()\n",
    "        # 扫描线\n",
    "        count = 0\n",
    "        res = 0\n",
    "        for i in arr:\n",
    "            if i[1] == -1:\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            res = max(res,count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        ops = []\n",
    "        for x in nums:\n",
    "            ops.append((x - k, -1))\n",
    "            ops.append((x + k, 1))\n",
    "        ops.sort()\n",
    "        cnt = 0\n",
    "        maxx = 0\n",
    "        for num, op in ops:\n",
    "            cnt -= op\n",
    "            maxx = max(maxx, cnt)\n",
    "        return maxx\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 1\n",
    "        xset=set()\n",
    "        for x in nums:\n",
    "            xset.add(x-k)\n",
    "            xset.add(x+k)\n",
    "        xs=sorted(xset)\n",
    "        n=len(xset)\n",
    "        diff=[0]*(n+1)\n",
    "        for x in nums:\n",
    "            l=bisect_left(xs,x-k)\n",
    "            r=bisect_left(xs,x+k)\n",
    "            diff[l]+=1\n",
    "            diff[r+1]-=1\n",
    "        return max(accumulate(diff))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        arr = []\n",
    "        for num in nums:\n",
    "            arr.append((num-k, 0))\n",
    "            arr.append((num+k, 1))\n",
    "        arr = sorted(arr)\n",
    "        beauty_val = 1\n",
    "        curr_val = 0\n",
    "        for pair in arr:\n",
    "            if pair[1] == 0:\n",
    "                curr_val += 1\n",
    "                beauty_val = max(beauty_val, curr_val)\n",
    "            else:\n",
    "                curr_val -= 1\n",
    "        return beauty_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        tmp = []\n",
    "        res = 0 \n",
    "        for i in range(len(nums)):\n",
    "            tmp.append([nums[i] - k, nums[i] + k])\n",
    "        tmp.sort()\n",
    "        queue = deque([])\n",
    "        for i in range(len(tmp)):\n",
    "            while queue and queue[0][1] < tmp[i][0]:\n",
    "                queue.popleft()\n",
    "            queue.append([tmp[i][0], tmp[i][1]])\n",
    "            res = max(res, len(queue))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        n=len(nums)\n",
    "        start={}\n",
    "        end={}\n",
    "        for num in nums:\n",
    "            start[num-k]=start.get(num-k,0)+1\n",
    "            end[num+k]=end.get(num+k,0)+1\n",
    "\n",
    "        # print(start[0][1])\n",
    "        maxB=0\n",
    "        res=0\n",
    "        for val in range(nums[0]-k,nums[n-1]+k+2):\n",
    "            if val in start:\n",
    "                # print('start  ',val)\n",
    "                res+=start[val]\n",
    "            if val-1 in end:\n",
    "                # print('end  ',val)\n",
    "                res-=end[val-1]\n",
    "            maxB=max(maxB,res)\n",
    "        return maxB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        n=len(nums)\n",
    "        start={}\n",
    "        end={}\n",
    "        for num in nums:\n",
    "            start[num-k]=start.get(num-k,0)+1\n",
    "            end[num+k]=end.get(num+k,0)+1\n",
    "\n",
    "        # print(start[0][1])\n",
    "        maxB=0\n",
    "        res=0\n",
    "        for val in range(nums[0]-k,nums[n-1]+k+2):\n",
    "            if val in start:\n",
    "                print('start  ',val)\n",
    "                res+=start[val]\n",
    "            if val-1 in end:\n",
    "                print('end  ',val)\n",
    "                res-=end[val-1]\n",
    "            maxB=max(maxB,res)\n",
    "        return maxB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        points = []\n",
    "        for num in nums:\n",
    "            points.append([num-k, 0])\n",
    "            points.append([num+k, 1])\n",
    "        points.sort()\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for point in points:\n",
    "            if point[1] == 0:\n",
    "                cur += 1\n",
    "            elif point[1] == 1:\n",
    "                cur -= 1\n",
    "            res = max(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        n =len(nums)\n",
    "        x = Counter()\n",
    "        res = []\n",
    "        start = inf\n",
    "        end = 0\n",
    "        for i in range(n):\n",
    "            x[nums[i] - k] += 1\n",
    "            x[nums[i] + k + 1] -= 1\n",
    "            start =min(start,nums[i] - k)\n",
    "            end = max(end,nums[i] + k)\n",
    "        ans = 1\n",
    "        cnt = 0\n",
    "        for i in range(start,end + 1):\n",
    "            if x[i] !=0:\n",
    "                cnt += x[i]\n",
    "                ans = max(ans, cnt)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        ans, mn, mx = 0, math.inf, -math.inf\n",
    "        for x in nums:\n",
    "            cnt[x - k] += 1\n",
    "            cnt[x + k + 1] -= 1\n",
    "            mn = min(mn, x - k)\n",
    "            mx = max(mx, x + k + 1)\n",
    "        res = 0\n",
    "        for k in range(mn, mx):\n",
    "            res += cnt[k]\n",
    "            ans = max(ans, res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, nums: List[int], k: int) -> int:\n",
    "        # 求出区间的最大交集\n",
    "        diff = defaultdict(int)\n",
    "        for n in nums:\n",
    "            diff[n-k] += 1\n",
    "            diff[n+k+1] -= 1\n",
    "        k = sorted(diff.keys())\n",
    "        s, ans = 0,-1\n",
    "        for p in k:\n",
    "            s += diff[p]\n",
    "            ans = max(s, ans)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
